//给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。 
//
// 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10⁴ 。 
//
// 
//
// 示例 1： 
//
// 
//输入：expression = "2-1-1"
//输出：[0,2]
//解释：
//((2-1)-1) = 0 
//(2-(1-1)) = 2
// 
//
// 示例 2： 
//
// 
//输入：expression = "2*3-4*5"
//输出：[-34,-14,-10,-10,10]
//解释：
//(2*(3-(4*5))) = -34 
//((2*3)-(4*5)) = -14 
//((2*(3-4))*5) = -10 
//(2*((3-4)*5)) = -10 
//(((2*3)-4)*5) = 10
// 
//
// 
//
// 提示： 
//
// 
// 1 <= expression.length <= 20 
// expression 由数字和算符 '+'、'-' 和 '*' 组成。 
// 输入表达式中的所有整数值在范围 [0, 99] 
// 
// Related Topics递归 | 记忆化搜索 | 数学 | 字符串 | 动态规划 
//
// 👍 739, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

class DifferentWaysToAddParentheses {
    public static void main(String[] args) {
        Solution solution = new DifferentWaysToAddParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Map<String, List<Integer>> memo = new HashMap<>();  // 备忘录提高效率

        // 分治算法参照labuladong：https://labuladong.gitee.io/algo/4/33/123/
        public List<Integer> diffWaysToCompute(String expression) {
            if (memo.containsKey(expression)) {
                return memo.get(expression);
            }

            // 对符号进行分割
            List<Integer> res = new LinkedList<>();
            for (int i = 0; i < expression.length(); i++) {
                char c = expression.charAt(i);
                if (c == '+' || c == '-' || c == '*') {
                    // 开始递归分支，依次对expression的符号进行分开
                    List<Integer> leftList = diffWaysToCompute(expression.substring(0, i));
                    List<Integer> rightList = diffWaysToCompute(expression.substring(i + 1));
                    // 开始治之
                    // 判断对什么符号进行的分开
                    // 通过子问题的结果，合成原问题的结果
                    for (Integer left : leftList)
                        for (Integer right : rightList)
                            // 进行计算
                            if (c == '+') res.add(left + right);
                            else if (c == '-') res.add(left - right);
                            else if (c == '*') res.add(left * right);
                }
            }

            // 如果为空，表示没有运算符，有运算符一定会出现结果
            if (res.isEmpty()) {
                res.add(Integer.parseInt(expression));
            }

            memo.put(expression, res);

            // 注意合并的时候返回的是res，所以合并的时候就没有运算符了，只有多种结果
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
